1741F - Multi-Colored Segments - CodeForces Solution

t = int(input())
def dist(i,j):
    if i >= j:
        return 0
    else:
        return j-i

while t > 0:
    n = int(input())
    seg = []
    for i in range(n):
        seg.append(list(map(int,input().split()))+[i+1])
    seg.sort(key=lambda x:(x[0],x[1]))
    color = {}
    i = 0
    while i < n:
        if seg[i][2] in color:
            if seg[i][2] == seg[i-1][2]:
                j = i
                while j < n-1 and seg[j][2] == seg[j+1][2]:
                    j = j + 1
                color[seg[i][2]][-1][1] = j+1
                for k in range(i,j+1):
                    color[seg[i][2]].append([k,j+1])
                i = j+1
                continue
            else:
                color[seg[i][2]].append([i,i+1])
                i = i + 1
        else:
            color[seg[i][2]] = [[i,i+1],]
            i = i + 1
    mindis= [1000000000]*(n+1)
    signal = [0]*(n+1)
    nowmaxj = [[0,0],[0,0]]
    i = 0
    while i < n:
        nowcolor = seg[i][2]
        u = signal[nowcolor]
        end = color[nowcolor][u][1]
        signal[nowcolor] += end - i
        maxj = 0
        if end != n:
            for j in range(i,end):
                maxj = max(maxj,seg[j][1])
                mindis[seg[j][3]] = min(mindis[seg[j][3]],dist(seg[j][1],seg[end][0]))
                for k in range(2):
                    if nowmaxj[k][1] != 0 and nowmaxj[k][1] != nowcolor:
                        mindis[seg[j][3]] = min(mindis[seg[j][3]],dist(nowmaxj[k][0],seg[j][0]))
        else:
            for j in range(i,end):
                for k in range(2):
                    if nowmaxj[k][1] != 0 and nowmaxj[k][1] != nowcolor:
                        mindis[seg[j][3]] = min(mindis[seg[j][3]],dist(nowmaxj[k][0],seg[j][0]))
            break
        if maxj > nowmaxj[0][0]:
            if nowmaxj[0][1] == nowcolor:
                nowmaxj[0][0] = maxj
            else:
                nowmaxj[1][0] = nowmaxj[0][0]
                nowmaxj[1][1] = nowmaxj[0][1]
                nowmaxj[0] = [maxj,nowcolor]
        elif maxj > nowmaxj[1][0]:
            if nowcolor != nowmaxj[0][1]:
                nowmaxj[1] = [maxj,nowcolor]
        i = end

    print(" ".join(map(str,mindis[1:])))
    t = t - 1